import java.util.Deque;
import java.util.LinkedList;

public class Sort {
    /**
     * 时间复杂度O(n^2)
     *    最好的情况下时间复杂度：O(n)
     *     当数据基本有序时，直接插入排序速度很快
     *      一般使用场景就是，数据基本趋于有序，建议使用直接插入排序
     *
     *     空间复杂度O(1)
     *     稳定性：稳定
     * @param array
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int j = i - 1;
            int tmp = array[i];
            while (j != -1) {
                if (array[j] > tmp) {
                    array[j+1] = array[j];
                    j--;
                } else {
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    public static void shellSort(int[] array) {
        int gap = array.length;
        while(gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);
    }

    /**
     * 时间复杂度： O(n^1.3-O(n^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     * @param gap
     */
    public static void shell(int[] array,int gap) {
        for (int  i = gap; i < array.length; i++) {
            int j = i - gap;
            int tmp = array[i];
            while (j >= 0) {
                if (array[j] > tmp) {
                    array[j+gap] = array[j];
                    j -= gap;
                } else {
                    array[j+gap] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    /**
     * 时间复杂度：O(n^2)
     *空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    public static void swap(int[] array,int i, int j) {
          int tmp  = array[i];
          array[i] = array[j];
          array[j] = tmp;
    }
    public static void heapSort(int[] array) {

    }
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flg  =  false;
            for (int j = 0; j  < array.length - 1 - i; j++) {
                if (array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if (flg == false) {
                return ;
            }
        }
    }
   public static void quickSort(int[] array) {
         int start = 0;
         int end = array.length - 1;
         quick(array,start,end);

   }
   public static void quick(int[] array,int start,int end) {
        if (start >= end) {
            return ;
        }
        int index = midThree(array,start,end);
        swap(array,start,index);
        int pivot = partition1(array,start,end);

        quick(array,start,pivot - 1);
        quick(array,pivot + 1,end);
   }
    private static int midThree(int[] array,int left,int right) {
        int mid = (left+right) / 2;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            //array[left] > array[right]
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }

    }
   //挖坑法
   public static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
           while (left < right && array[right] >= tmp) {
               right--;
           } //找到比tmp小的下标
            array[left]  = array[right];
           while (left < right && array[left] <= tmp) {
               left++;
           } //找到比tmp大的下标
           array[right] = array[left];
       }
        array[left] = tmp;
        return  left;
   }

   //hoare法
   public static int partition1(int[] array,int left,int right) {
           int tmp = array[left];
           int i = left;
           while (left < right) {
               while (left < right && array[right] >= tmp) {
                   right--;
               }
               while (left < right && array[left] <= tmp) {
                   left++;
               }
               swap(array,left,right);
           }
           swap(array,left,i);
           return left;
   }
    //前后指针法 【了解即可】
    private static int partition3(int[] array,int left,int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }
    //非递归实现快排
    public static void quickSort1(int[] array) {
        Deque<Integer> stack = new LinkedList<>();
         int left = 0;
         int right = array.length - 1;
         int pivot = partition(array,left,right);
         if (pivot > left + 1) {
             stack.push(left);
             stack.push(pivot - 1);
         }
         if (pivot < right-1) {
             stack.push(pivot+1);
             stack.push(right);
         }
         while (!stack.isEmpty()) {
              right = stack.pop();
              left = stack.pop();
              pivot = partition(array,left,right);
             if (pivot > left + 1) {
                 stack.push(left);
                 stack.push(pivot - 1);
             }
             if (pivot < right-1) {
                 stack.push(pivot+1);
                 stack.push(right);
             }
         }
    }
    //归并排序
    public static void mergeSort(int[] array) {
          mergeSortFunc(array,0,array.length-1);
    }
    public static void mergeSortFunc(int[] array,int left,int right) {
        if (left >= right) {
            return ;
        }
        int mid = (left + right) / 2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);
    }
    public static void merge(int[] array,int start,int end,int mid) {
        int s1 = start;
        //int e1 = mid;
        int s2 = mid+1;
        //int e2 = end;
        int[] tmp = new int[end-start+1];
        int k = 0;//tmp数组的下标
        while (s1 <= mid && s2 <= end) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= end) {
            tmp[k++] = array[s2++];
        }

        for (int i = 0; i < tmp.length; i++) {
            array[i+start] = tmp[i];
        }
    }
}
